package com.johann.leetcode;

public class T42_ReceiveWater {
    public int trap(int[] height) {
        int len= height.length;
        if(len<=2) return 0;
        int water = 0;
        int leftHighestBound = height[0];
        int rightHighestBound = height[len-1];
        int i=1;
        int j=len-2;
        while(i<=j){
            leftHighestBound = Math.max(leftHighestBound,height[i-1]);
            rightHighestBound = Math.max(height[j+1],rightHighestBound);
            if(leftHighestBound<rightHighestBound){
                water = water + Math.max(Math.min(leftHighestBound,rightHighestBound)-height[i],0);
                i++;
            }else if(leftHighestBound>rightHighestBound){
                water = water + Math.max(Math.min(leftHighestBound,rightHighestBound)-height[j],0);
                j--;
            }else{
                water = water + Math.max(Math.min(leftHighestBound,rightHighestBound)-height[i],0);
                water = water + Math.max(Math.min(leftHighestBound,rightHighestBound)-height[j],0);
                i++;
                j--;
            }
        }
        return water;
    }

    public static void main(String[] args) {
        System.out.println(new T42_ReceiveWater().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }
}
